package org.thewares.collection.test;

import org.scalatest.Spec;
import org.scalatest.matchers.ShouldMatchers;
import org.scalatest.prop.Checkers;


object TestDeck {

      type TitledDeque=Titled[Deque[Int]];
      class TestDeck(td:TitledDeque) extends Spec with ShouldMatchers with Checkers {
	    val empty=td.empty;
	    println(td.title+"==========");

	    describe("A Deque") {
		  val nil:List[Int]=Nil;

		  it("should be list like") {
			val q = 2 :: 1 :: empty;
			q.head should equal (2)
			q.tail.head should equal (1)
			check((list: List[Int]) =>{
			      var queue=(empty /: list) {case (q:Deque[Int],element:Int) => element::q};
			      var popped=nil;
			      for (i <- 1 to list.length){
				    popped = queue.head :: popped;
				    queue= queue.tail;
			      }
			      popped==list
			})
			
		  }

		  it("should be stack like") {
			val stack = empty.push(1).push(2);
			stack.peek should equal (2)
			stack.pop.peek should equal (1)
			check((list: List[Int]) =>{
			      var fullStack=(empty /: list) {case (stack:Deque[Int],element:Int) => stack.push(element)};
			      //	      println("list: "+list);
			      //      println("q:    "+fullStack);
			      var popped=nil;
			      for (i <- 1 to list.length){
				    popped = fullStack.peek :: popped;
				    fullStack= fullStack.pop;
			      }
			      popped==list
			}
			)      
		  }

		  it("should be queue like") {
			val q = empty.enqueue(1).enqueue(2);
			q.dequeue._1 should equal (1)
			q.tail.head should equal (2)
			check((list: List[Int]) =>{
			      var queue=(empty /: list) {case (q:Deque[Int],element:Int) => q.enqueue(element)};
			      var popped=nil;
			      for (i <- 1 to list.length){
				    popped = queue.head :: popped;
				    queue= queue.tail;
			      }
			      popped==list.reverse
			}
			)      
		  }


		  it("pushing leaves things in order") {
			check{
			      (list: List[Int]) => {
				    val stack=(empty /: list) {case (stack:Deque[Int],element:Int) => stack.push(element)};
				    stack.elements.toList==list
			      }
			}
		  }
		  it("unshifting leaves things in  reverse order") {
			check{
			      (list: List[Int]) => {
				    val stack=(empty /: list) {case (stack:Deque[Int],element:Int) => stack.unshift(element)};
				    stack.elements.toList==list.reverse
				    
			      }
			}
		  }
		  // not all implementations support this 
		  it("should be confluent") {
			// length  check.
			check{
			      (list: List[Int]) => {
				    val stack=(empty /: list) {case (stack:Deque[Int],element:Int) => element :: stack};
				    var s:Deque[Int]=stack ++ stack;
				    var expected=stack.length *2;
				    val iterations=20;
				    
				    for (i<- 2 to iterations) {
					  //					  println("Stack is size "+s.length+", depth is "+s.depth+", nodes is "+s.nodes+
					  //					  ", expected is "+expected);
					  //					  println(s.state);
					  s ++= s;
					  expected *= 2;
				    }
				    val tsize=(stack.size * (1<<iterations));
				    val ret=(s.size == tsize);
				    //				    println("big size is "+s.length+ " expected is "+(tsize)+" see also "+s.size+": "+ret);
				    // println(s.state);
				    ret;				    
			      }
			}
			check{
			      (list: List[Int]) => {
				    val dq=(empty /: list) {case (d:Deque[Int],e:Int) => d.push(e)};				    
				    val biglist= list ::: 101 :: list ::: 102 :: list ::: 103 :: list;
				    val bigdeck= dq ::: 101 :: dq ::: 102 :: dq ::: 103 :: dq;
				    bigdeck.elements.toList==biglist;
			      }
			}
		  }
		  it("should support apply") {
			check{
			      (front: List[Int],elem:Int, back:List[Int]) => {
				    val biglist= front ::: elem :: back 
				    val dq=(empty /: biglist) {case (d:Deque[Int],e:Int) => d.push(e)};
				    dq(front.length)==elem;
			      }
			}
		  }
		  it("should support length") {
			check{
			      (front: List[Int], back:List[Int]) => {
				    val dq1=(empty /: front) {case (d:Deque[Int],e:Int) => e :: d};
				    val dq=(dq1 /: back) {case (d:Deque[Int],e:Int) => e :: d};
				    dq.length==(front.length+back.length);
			      }
			}
		  }
		  it("should support elements and reverseElements") {
			check{
			      (list: List[Int]) => {
				    val dq=(empty /: list) {case (d:Deque[Int],e:Int) => d.push(e)};
				    dq.elements.toList.reverse==dq.reverseElements.toList
			      }
			}
		  }

	    }
      }
      
      def speed(td:TitledDeque)={
	    (new TimeDeque(td)).execute
      }
      def sound(td:TitledDeque)={
	    (new TestDeck(td)).execute
      }
      
      def main(argv:Array[String]):Unit = {
	    val longList=false;
	    val candidates=
		  if (longList) {
			List[Titled[Deque[Int]]](
			      Titled("ListFour",nodal.Nodes.EmptyLittleListFour),
			      Titled("ListEight",nodal.Nodes.EmptyLittleListEight),
			      Titled("ListSixteen",nodal.Nodes.EmptyLittleListSixteen),
			      //		  TitledDeque("ListThirtyTwo",nodal.Nodes.EmptyLittleListThirtyTwo),
			      Titled("Two",nodal.Nodes.EmptyTwo),
			      //		  TitledDeque("Three",nodal.Nodes.EmptyThree),
			      Titled("Four",nodal.Nodes.EmptyFour),
			      //		  TitledDeque("Five",nodal.Nodes.EmptyFive),
			      Titled("Six",nodal.Nodes.EmptySix),
			      //		  TitledDeque("Seven",nodal.Nodes.EmptySeven),
			      Titled("Eight",nodal.Nodes.EmptyEight),
			      Titled("Sixteen",nodal.Nodes.EmptySixteen),
			      Titled("ThirtyTwo",nodal.Nodes.EmptyThirtyTwo),
			      Titled("SixtyFour",nodal.Nodes.EmptySixtyFour),
			      Titled("Thgie",ReverseDeque(nodal.Nodes.EmptyEight)),
			      Titled("Deck",baseline.Deck.empty),
			      //				TitledDeque("Deck24",deck24.Deck.empty),
			      //				TitledDeque("Deck16",deck16.Deck.empty),
			      //				TitledDeque("Deck8",deck8.Deck.empty),
			      Titled("FingerTree",finger.FingerTree.EmptySeq),
			      Titled("AlphaDeque",Deque.empty)
			      //		  TitledDeque("FingerTree2",finger2.FingerTree.empty)
			      //TitledDeque("Literature",literature.Literature.EmptyCat)
			);
		  } else {
			List[Titled[Deque[Int]]](
			      Titled("FingerTree",finger.FingerTree.EmptySeq),
			      Titled("AlphaDeque",Deque.empty)
			);
		  };
	    candidates.map(sound(_));
	    candidates.map(speed(_));
	    if (true){
		  (new TimeBitVector).execute;
		  (new TimeList).execute;
		  (new TimeArrayBuffer).execute;
		  (new TimeQueue).execute;
	    }

      }
}


